package tiruvury.InterviewPrep.SortAndSearch;

public class SortAndSearch
{
	public static int[] BubbleSort(int[] arr)
	{
		int len = arr.length;
		int temp = 0;
		for (int i = 0; i < len; i++)
		{
			for (int j = 0; j < len - i; j++)
			{
				if ((j + 1) < (len - i))
				{
					if (arr[j] > arr[j + 1])
					{
						temp = arr[j];
						arr[j] = arr[j + 1];
						arr[j + 1] = temp;
					}
				}
			}
		}

		return arr;
	}

	public static int[] SelectionSort(int[] arr)
	{
		int minIdx = -1;
		int temp = 0;

		for (int i = 0; i < arr.length; i++)
		{
			minIdx = i;
			for (int j = i + 1; j < arr.length; j++)
			{
				if (arr[minIdx] > arr[j])
				{
					minIdx = j;
				}
			}
			temp = arr[i];
			arr[i] = arr[minIdx];
			arr[minIdx] = temp;
		}
		return arr;
	}

	public static int[] MergeBIntoA(int[] a, int[] b)
	{
		int i = a.length - 1;
		int j = b.length - 1;
		int k = i + j + 1;

		int[] c = new int[a.length + b.length];

		for (int x = 0; x < a.length; x++)
		{
			c[x] = a[x];
		}

		while (k >= 0)
		{
			if (i >= 0 && j >= 0)
			{
				if (a[i] >= b[j])
				{
					c[k] = a[i];
					i--;
				}
				else
				{
					c[k] = b[j];
					j--;
				}
			}
			else if (j >= 0)
			{
				c[k] = b[j];
				j--;
			}
			else
			{
				// i>=0
				// no more merging from B to A, so stop
				break;
			}
			k--;
		}

		return c;
	}
}
